package com.platform.modules.alg.alglib.poj3294;

public class Poj3294 {
    // 100 个字符串中间添加了 100 个，每个字符串最大 1000
    private int maxn = 100500;
    int belong[] = new int[maxn];
    int r[] = new int[maxn];
    int sa[] = new int[maxn];
    String s = "";
    // 名称数组
    int rank[] = new int[maxn];
    // 高度数组
    int height[] = new int[maxn];
    int n, k;
    int wa[] = new int[maxn];
    int wb[] = new int[maxn];
    int wv[] = new int[maxn];
    // c[]用于基数排序统计
    int c[] = new int[maxn];

    boolean cmp(int r[], int a, int b, int l) {
        return (r[a] == r[b]) && (r[a + l] == r[b + l]);
    }

    // 交换两个数组的内容 https://blog.csdn.net/m0_56793367/article/details/115599564
    public static void swap(int[] array1, int[] array2) {
        int tmp = 0;
        for (int i = 0; i < array1.length; i++) {
            tmp = array1[i];
            array1[i] = array2[i];
            array2[i] = tmp;
        }
    }

    void da(int r[], int sa[], int n, int m) {
        int i, k, p;
        int x[] = wa;
        int y[] = wb;
        for (i = 0; i < m; i++) // 基数排序
            c[i] = 0;
        for (i = 0; i < n; i++)
            c[x[i] = r[i]]++;
        for (i = 1; i < m; i++)
            c[i] += c[i - 1];
        for (i = n - 1; i >= 0; i--)
            sa[--c[x[i]]] = i;
        for (k = 1; k <= n; k <<= 1) {
            // 直接利用 sa 排序第二关键字
            p = 0;
            for (i = n - k; i < n; i++)
                y[p++] = i; // 补零的位置下标排在最前面
            for (i = 0; i < n; i++)
                if (sa[i] >= k)
                    y[p++] = sa[i] - k;
            // 基数排序第一关键字
            for (i = 0; i < n; i++)
                wv[i] = x[y[i]]; // 将第二关键字排序结果转换为名次，进行排序
            for (i = 0; i < m; i++)
                c[i] = 0;
            for (i = 0; i < n; i++)
                c[wv[i]]++;
            for (i = 1; i < m; i++)
                c[i] += c[i - 1];
            for (i = n - 1; i >= 0; i--)
                sa[--c[wv[i]]] = y[i];
            // 根据 sa 和 x 数组，重新计算新的x数组
            swap(x, y); // y 数组已经没有用，更新x需要使用x本身数据，因此放入y使用
            p = 1;
            x[sa[0]] = 0;
            for (i = 1; i < n; i++)
                x[sa[i]] = cmp(y, sa[i - 1], sa[i], k) ? p - 1 : p++;
            if (p >= n)//排序结束
                break;
            m = p;
        }
    }

    void calheight(int r[], int sa[], int n) {
        int i, j, k = 0;
        for (i = 1; i <= n; i++)
            rank[sa[i]] = i;
        for (i = 0; i < n; i++) {
            if (k > 0)
                k--;
            j = sa[rank[i] - 1];
            while (r[i + k] == r[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

    boolean check(int mid, int n, int m, boolean flag) {
        int i = 2;
        boolean vis[];
        while (true) {
            vis = new boolean[105]; // 清零
            while (i <= n && height[i] < mid)
                i++;
            if (i > n)
                break;
            vis[belong[sa[i - 1]]] = true;//标记该字符串
            while (i <= n && height[i] >= mid) {
                vis[belong[sa[i]]] = true;//如果是自己的子串，只标记一次
                i++;
            }
            int cnt = 0;
            for (int j = 1; j <= m; j++)
                if (vis[j])
                    cnt++;
            if (cnt > m / 2) {
                if (!flag)
                    return true; // 立即返回1，否则输出，继续运行输出所有满足条件的子串
                else {
                    for (int j = sa[i - 1], t = 0; t < mid; j++, t++)
                        output += s.charAt(j);
                    output += "\n";
                }
            }
        }
        return false;
    }

    void solve(int L, int R) {
        int res = -1, mid;
        while (L <= R) {
            mid = (L + R) >> 1;
            if (check(mid, n, k, false)) {
                res = mid;
                L = mid + 1;
            } else
                R = mid - 1;
        }
        if (res == -1)
            output += "?\n";
        else
            check(res, n, k, true);//输出
    }

    public String output = "";

    public String cal(String input) {
        int len = 0;
        String[] line = input.split("\n");
        int count = 0;
        while (true) {
            s = "";
            k = Integer.parseInt(line[count++]);
            if (k == 0) {
                return output;
            }

            n = 0;
            for (int i = 1; i <= k; i++) { // 将 k 个字符串连接起来，中间用特殊字符间隔
                String str = line[count];
                count++;
                this.s += str;
                if (i == 1)
                    len = this.s.length();
                for (int j = 0; j < str.length(); j++) {
                    belong[n] = i; // 标记属于第 i 个字符串
                    r[n] = str.charAt(j) - 'a' + 1;//a-z 97-122
                    n++;
                }
                this.s += "#"; // 35
                r[n] = 100 + i;
                n++;
            }
            n--;
            r[n] = 0; // 末尾补一个比所有值都小的数
            da(r, sa, n + 1, 300);
            calheight(r, sa, n);
            solve(1, len);
            output += "\n";
        }
    }
}
